#ifndef _NETWORK_CPP_
#define _NETWORK_CPP_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXVERTEX 200
#define MAXEDGE 1000

// 顶点结构体
typedef struct Vertex
{
	int id;				  // 顶点编号（唯一）
	int degree;			  // 顶点的度
	int edges[MAXVERTEX]; // 顶点上的边数组,内含边编号
	short change_path	  // 允许的最大变通道数,最大为20
} Vertex;

// 边结构体
typedef struct Edge
{
	int id;	   // 边的编号（唯一）
	int h;	   // 边头顶点编号
	int t;	   // 边尾顶点编号
	int w;	   // 权值，即目前边上业务价值总和
	int k[40]; // 光纤通道
} Edge;

// 图结构体
typedef struct Graph
{
	Vertex v[MAXVERTEX]; // 顶点数组
	Edge e[MAXEDGE];	 // 边数组
	int nv;				 // 顶点数
	int ne;				 // 边数
	bool dirctional;	 // t:有向图，f:无向图
	bool weighted;		 // t:带权图，f:等权图
} Graph;

typedef struct Job
{
	int begin_v;		  // 业务起点
	int end_v;			  // 业务终点
	int path_sum;		  // 经过的边数目
	int range_L;		  // 占用通道范围左
	int range_R;		  // 占用通道范围右
	int value;			  // 业务价值
	int path_id[MAXEDGE]; // 依次经过路径上的边编号
} Job;

#include "showgt.h"

// 从文件中读入图，在内存中生成图的表示
void initGraphFromFile(Graph *g, const char *gfile)
{
	FILE *fp = fopen(gfile, "r");
	if (!fp)
	{
		printf("read file cannot open!!\n");
		exit(0);
	}
	char bv[10];
	// 读取图的基本信息
	fscanf(fp, "%u%u%s", &(g->nv), &(g->ne), bv);
	// printf("%d %d %s", g->ne, g->nv, bv);
	g->weighted = strcmp(bv, "true") == 0 ? true : false;
	fscanf(fp, "%s", bv);
	g->dirctional = strcmp(bv, "true") == 0 ? true : false;
	// 读取顶点信息
	for (int i = 0; i < g->nv; i++)
	{
		fscanf(fp, "%d", &(g->v[i].id));
		g->v[i].degree = 0;
		// printf("顶点%d-权%d\n", g->v[i].id, g->v[i].w);
	}
	// 读取边信息
	for (unsigned long i = 0; i < g->ne; i++)
	{
		fscanf(fp, "%u%u%d", &(g->e[i].h), &(g->e[i].t), &(g->e[i].w));
		// printf("边:%u-%u=>%d\n", g->e[i].h, g->e[i].t, g->e[i].w);
		g->e[i].id = i;
		unsigned h, t;
		h = g->e[i].h;
		t = g->e[i].t;
		g->v[h].edges[g->v[h].degree++] = i;
		if (g->dirctional == false)
			g->v[t].edges[g->v[t].degree++] = i;
	}
	fclose(fp);
}

// 生成一个空图
Graph *initGraph(bool directional, bool weighted)
{
	Graph *g = (Graph *)malloc(sizeof(Graph));
	g->nv = g->ne = 0;
	g->dirctional = directional;
	g->weighted = weighted;
	return g;
}

// 打印邻接表的信息
void printgraph(Graph *g)
{
	printf("basic information of Graph:vertix(%u)-edge(%lu)-%s-%s\n", g->nv, g->ne, g->weighted ? "weighted graph" : "nonweighted", g->dirctional ? "dirctional" : "nondirctional");
	for (int i = 0; i < g->nv; i++)
	{
		printf("ID(%u)-degrees(%d)-t(eid|w):%u", g->v[i].id, g->v[i].degree, g->v[i].id);
		for (int j = 0; j < g->v[i].degree; j++)
		{
			unsigned long e = g->v[i].edges[j];
			if (g->v[i].id == g->e[e].h)
				printf("->%u(%d)", g->e[e].t, g->e[e].w);
			else
				printf("->%u(%d)", g->e[e].h, g->e[e].w);
		}
		printf("\n");
	}
}

// 查找给定编号的边，返回其两个顶点
int getVexByEdgeHead(Graph *g, int id)
{
	int pos = 0;
	for (int i = 0; i < g->ne; i++)
		if (g->e[i].id == id)
		{
			pos = g->e[i].h;
			return pos;
		}
	printf("input wrong edge id in getVexByEdgeTail()!\n");
	exit(0);
}
int getVexByEdgeTail(Graph *g, int id)
{
	int pos = 0;
	for (int i = 0; i < g->ne; i++)
		if (g->e[i].id == id)
		{
			pos = g->e[i].t;
			return pos;
		}
	printf("input wrong edge id in getVexByEdgeTail()!\n");
	return -1;
}

// 查找给定编号的顶点，返回其顶点数组下标
int getVexIdx(Graph *g, int id)
{
	for (int i = 0; i < g->nv; i++)
		if (g->v[i].id == id)
			return i;
	printf("input wrong vertex id in getVexIdx()!\n");
	// exit(0);
}

// 查找给定编号的顶点，返回其度
int getVexDegree(Graph *g, int id)
{
	for (int i = 0; i < g->nv; i++)
		if (g->v[i].id == id)
			return g->v[i].degree;
	printf("input wrong vertex id in getVexDegree()!\n");
	exit(0);
}

// 查找给定编号的顶点,返回其所有边
int *getEdgesByNode(Graph *g, int id, int *ne)
{
	for (int i = 0; i < g->nv; i++)
		if (g->v[i].id == id)
		{
			*ne = g->v[i].degree;
			return g->v[i].edges;
		}
	printf("input wrong vertex id in getEdgesByNode()!\n");
	exit(0);
}

// 查找给定编号的边，返回其边数组下标
int getEdgeIdx(Graph *g, int id)
{
	for (int i = 0; i < g->ne; i++)
		if (g->e[i].id == id)
			return i;
	// printf("input wrong edge id in getEdgeIdx()!\n");
	// exit(0);
}

// 查找给定编号的边，返回其权值
int getEdgeW(Graph *g, int id)
{
	for (int i = 0; i < g->ne; i++)
		if (g->e[i].id == id)
			return g->e[i].w;
	printf("input wrong edge id in getEdgeW()!\n");
	exit(0);
}

// 查找给定编号的边，返回其两个顶点
void getVexByEdge(Graph *g, int id, int *h, int *t)
{
	for (int i = 0; i < g->ne; i++)
		if (g->e[i].id == id)
		{
			*h = g->e[i].h;
			*t = g->e[i].t;
		}
	// printf("input wrong edge id in getVexByEdge()!\n");
	// exit(0);
}

// 删除边
void deleteEdge(Graph *g, int id)
{
	// 将将要删除的边查找出来为e
	int e_idx = getEdgeIdx(g, id);
	Edge e = g->e[e_idx];
	// 通过将最后一个边转移到e_idx位置来达到删除的目的
	g->e[e_idx] = g->e[--(g->ne)];
	// 修改尾结点的信息
	int t_idx = getVexIdx(g, e.t);
	Vertex t = g->v[t_idx];
	for (int i = 0; i < t.degree; i++)
	{
		if (t.edges[i] == id)
		{
			t.edges[i] = t.edges[--(t.degree)];
		}
	}
	// 修改头结点的信息
	int h_idx = getVexIdx(g, e.h);
	Vertex h = g->v[h_idx];
	for (int i = 0; i < h.degree; i++)
	{
		if (h.edges[i] == id)
		{
			h.edges[i] = h.edges[--(h.degree)];
		}
	}
}

#endif